<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>哈希表实现(链地址法实现)</title>
</head>
<body>
<script>
    function HashTable() {
        //用于储存的数组
        this.storage = [];

        //记录数据个数
        this.count = 0;

        //记录数组总长度
        this.limit = 7;

        HashTable.prototype.put = function (key, value) {
            // 1.根据key取得对应的index
            const index = hashCode(key, this.limit);

            // 2.根据下标位置找到对应的bucket(数组，用来存多个 index相同的 键值组),并且判断该下标位置是否已有数据（也是是否已有bucket）
            let bucket = this.storage[index];
            if (bucket === undefined) {
                bucket = [];
                this.storage[index] = bucket;
            }

            // 3.判断该bucket里是否已经存在相同key的value，如果有则修改
            for(let i = 0; i < bucket.length; i++) {
                let tuple = bucket[i];
                if (tuple[0] === key) { //bucket也是用数组存的键值对，下标0存key，下标1存value
                    tuple[1] = value;
                    return
                }
            }

            // 4.执行到这里说明是添加操作
            bucket.push([key, value]);
            this.count += 1;

            // 5.判断是否需要扩容
            if (this.count > this.limit * 0.75) {
                this.resize(getPrimeNumber(this.limit * 2));
            }
        };

        HashTable.prototype.get = function (key) {
            // 1.拿到对应下标位置
            let index = hashCode(key, this.limit);

            // 2.下标拿到对应的bucket
            let bucket = this.storage[index];

            // 3.如果为undefined说明没有存这个key对应的value
            if (bucket === undefined) {
                console.log(true);
                return null;
            }

            // 4.循环bucket找key对应的value
            for (let i = 0; i < bucket.length; i++) {
                if(key === bucket[i][0]) {
                    return bucket[i][1]
                }
            }

            // 5.没有找到返回null
            return null;

        };

        HashTable.prototype.remove = function (key) {
            let index = hashCode(key, this.limit);
            let bucket = this.storage[index];
            if (bucket === undefined) {
                return false;
            }
            let tuple = false;
            for (let i = 0; i < bucket.length; i++) {
                if (key === bucket[i][0]) {
                    this.count -= 1;
                    tuple = bucket.splice(i, 1);
                }
            }
            //判断是否需要缩小容量
            if (this.limit > 7 && this.count < this.limit * 0.25) {
                this.resize(getPrimeNumber(Math.floor(this.limit / 2)));
            }
            return tuple[0][1];
        };

        HashTable.prototype.isEmpty = function () {
            return this.count === 0;
        };

        HashTable.prototype.size = function () {
            return this.count;
        };

        /**
         * 哈希表扩容缩容操作
         * @param newLimit 扩容的大小
         */
        HashTable.prototype.resize = function (newLimit) {
            // 1.保存旧的数组内容
            let oldStorage = this.storage;

            // 2.重置属性
            this.storage = [];
            this.count = 0;
            this.limit = newLimit;

            // 3.遍历oldStorage中所有的bucket
            for (let i = 0; i < oldStorage.length; i++) {
                // 3.1取出对应bucket
                let bucket = oldStorage[i];
                // 3.2判断bucket是否有，没有进行下一轮遍历
                if (bucket === undefined) {
                    continue
                }
                //3.取出bucket插入到新数组
                for (let j = 0; j < bucket.length; j++) {
                    this.put(bucket[j][0], bucket[j][1]);
                }
            }
            console.log("扩容到" + newLimit);
        };

        function hashCode(str, size) {
            let hashCode = 0;
            for (let i = 0; i < str.length; i++) {
                hashCode = 37 * hashCode + str.charCodeAt(i);
            }
            return hashCode % size;
        }

        /**
         * 判断一个数是否为质数
         * @param num
         * @returns {boolean}
         */
        function isPrimeNumber(num) {
            if (!typeof num instanceof Number) {
                throw "参数类型错误"
            }
            // 1. 获取num的平方根
            let temp = parseInt(Math.sqrt(num));

            // 2. 循环判断
            for (let i = 2; i <= temp; i++) {
                if (num % i === 0) {
                    return false;
                }
            }
            return true
        }

        /**
         * 找到距离参数最近的质数，递增找
         */
        function getPrimeNumber(num) {
            while (!isPrimeNumber(num)) {
                num += 1;
            }
            return num;
        }

    }


    let hashTable = new HashTable();
    hashTable.put(1, "进击的巨人");
    hashTable.put(2, "寄生兽");
    hashTable.put(3, "小林家的龙女仆");
    hashTable.put(4, "override");
    hashTable.put(5, "鬼灭之刃");
    hashTable.put(6, "辉夜姬");
    console.log(hashTable.get(1));
    console.log(hashTable.remove(1));
    console.log(hashTable.get(1));
</script>
</body>
</html>